Content Addressable Memories are memories in which the data word is selected or identified by its contents rather than by its physical address. In other words, a CAM is a memory that can be instructed to compare a specific pattern of comparand or other reference data with data stored in the CAM array. The entire CAM array is searched in parallel for a match with the comparand data. CAMs are used in a variety of applications, such as sorting large databases, pattern-matching for image processing and voice recognition and cache systems of high speed computing systems. CAM cells are becoming increasingly popular in high-speed network routers and many other applications known in the art of computing.
A standard content addressable memory comprises an array of individual CAM cells. Each CAM cell consists of a data storage unit and comparison circuitry. A CAM cell can store a single bit of data and can compare the stored bit with a comparand or other reference bit during a search operation.
In a common implementation, each row represents a different word of maximum length having depth equal to the total number of columns in the CAM array. During the comparison operation, if all the reference bits match the corresponding stored data bits, a match is declared otherwise the match operation fails. An indicator, commonly known as a “Match Line” (“ML”), associated with each stored word indicates a match or mismatch, which can be detected by a sensing means connected to each ML.
In order to ensure proper functioning of the CAM, a built-in-self-test (“BIST”) is often implemented in the CAMs. However conventional methods for BIST implementation often require a large chip area and complex circuitry.
Turning to FIG. 1, illustrated is an exemplary prior art (U.S. Pat. No. 6,430,072) content addressable memory structure with BIST implementation in which the each matchline of the CAM is connected to one of the words, and a self-test matchline compare circuit is connected to the matchlines, adapted to individually test the match function for all of the words. Further, a matchline compare circuit having a plurality of XNOR gates or comparators 1.3a, 1.3b, 1.3c, 1.3d equal in number to the number of words, such that each word is connected to a dedicated comparator to allow each word in the memory array to be individually tested.
During test of the search function, matchline latches 1.1a, 1.1b, 1.1c, 1.1d are loaded with the match results for each word on the matchlines. The match compare shift register 1.2a, 1.2b, 1.2c, 1.2d has been loaded previously with the expected results of the search. Match compare shift register override multiplexers 1.5a, 1.5b, 1.5c, 1.5d are controlled by match compare shift register override select signal 1.6 and operate to select a logic value to which the matchlines will be compared, which will either come from the match compare shift register 1.2a, 1.2b, 1.2c, 1.2d, or the alternate match compare signal 1.4b. The XNOR gates 1.3a, 1.3b, 1.3c, 1.3d compare the results with the expected results, and logic gates 1.7, 1.8, 1.9 compress the compare results into compare signal 1.10 which is “active high” if the matchline values are equal to the expected values. The structure includes an equal number of the words, the first latches, the second latches, the multiplexers, and the comparators, such that each word's match function is individually tested. The override signal line carries a test data pattern that does not match data in any word in the memory array.
This prior art reference patent provides an extra latch and a XOR gate with each matchline in order to compare for match line contents that substantially increase the size and complexity of the memory chip. It is readily evident that there is a need for memory-built-in-self-test technique that is area efficient. It is also readily evident that a need exists for a MBIST that is not only area efficient, but also is simple to implement and is less expensive.